package my.algorithms;

import java.util.*;

public class General
{
    public static void main (String [] args)
    {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < 1000; i++)
        {
            list.add(i);
        }

        Random r = new Random(System.nanoTime());
        int remove = r.nextInt(1001);
        list.remove(remove);
        System.out.println("Removing " + remove);
        int [] array = new int [list.size()];
        for (int i = 0; i < list.size(); i++)
        {
            array[i] = list.get(i);
        }
        System.out.println("Found missing integer with gap algo " + findMissingGapDetection(array));
        System.out.println("Found missing integer with summation " + findMissingNumberInArray(array));
    }

    /**
     * Summation approach
     *
     * @param array
     * @return
     */
	public static int findMissingNumberInArray(int[] array)
	{
		// formula for summing number 1 ... n
		int total = (array.length + 1) * array.length / 2;

		int missingTotal = 0;
		for (int i = 0; i < array.length; i++)
		{
			missingTotal += array[i];
		}

		// the missing number will be here
		return total - missingTotal;
	}

    public static int findMissingGapDetection(int [] array)
    {
        int i = 1;
        if ((array[1] - array[0]) > 1) {return array[1] - 1;}
        while (i < array.length)
        {
            if((array[i] - array[i-1]) > 1) {return array[i] - 1;}
            i++;
        }
        return -1;
    }

	public static int findASingleDuplicate(int[] array)
	{
		// total minus 1 so we can see what has been added
		int total = (array.length + -1) * array.length / 2;

		// Note this if array isn't missing a value but actually has values
		// 1 ... n + an extra one
		int totalWithADuplicate = 0;
		for (int i = 0; i < array.length; i++)
		{
			totalWithADuplicate += array[i];
		}
		return totalWithADuplicate - total;
	}

	public static void findFirst2NumbersThatSumToN(int[] numbers, int n)
	{
		// Obvious brute force problem exists with double loop
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

		boolean found = false;
		int index1 = -1;
		int index2 = -1;
		for (int i = 0; i < numbers.length && !found; i++)
		{
			index1 = i;
			// Store the number <key=arrayValue,value=arrayIndex>
			map.put(numbers[i], i);

			// The other number needed to make the sum
			int numToCheckFor = n - numbers[i];

			// The index of that other number it exist
			index2 = (map.containsKey(numToCheckFor)) ? map.get(numToCheckFor)
					: -1;

			if (index2 != -1)
			{
				found = true;
			}
		}

		if (found)
		{
			System.out.println(numbers[index1] + " @ [" + index1 + "] + "
					+ numbers[index2] + " @ [" + index2 + "]");
		} else
		{
			System.out.println("Not found");
		}
	}

	public static void findDuplicatesInArray(int[] numbers)
	{
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		LinkedHashMap<Integer, Integer> duplicates = new LinkedHashMap<Integer, Integer>();

		for (int i = 0; i < numbers.length; i++)
		{
			// Check the map to see if it contains this value
			if (map.containsKey(numbers[i]))
			{
				// if it does store it with a count
				int count = duplicates.get(numbers[i]) + 1;
				duplicates.put(numbers[i], count);
			} else
			{
				// if it doesn't add it
				map.put(numbers[i], 1);
			}
		}

		// print the duplicates
		for (Integer theDup : duplicates.keySet())
		{
			System.out.println("Duplicate : " + theDup + " # of times : "
					+ duplicates.get(theDup));
		}
	}

	public static void findSubArrayWithinAnArray(int[] array, int[] subArray)
	{
		/*
		 * int current_sum = 0; 
    int max_sum = 0; 
    int begin_index = 1;  
   // Edit : (Variable No more reqd).  int end_index = 1; 
    int current_index = 1; 
    int max_begin_index = 1; // Edited 
    int max_end_index = 1;    // Edited 
   
    while(current_index <= n) 
    { 
         current_sum += Arr[current_index]; 
         if(current_sum > max_sum) 
         { 
              max_sum = current_sum; 
              max_end_index  = current_index; // Edited 
     max_begin_index = begin_index; // Edited 
          } 
         else if(current_sum < 0)  
         { 
                // EDIT : (Remove this line)  max_sum = 0; 
                 current_sum = 0; 
                 begin_index = current_index+1; 
                
        } 
        current_index++; 
    }                 
 
     if (max_begin_index > max_end_index) // edit 
     { 
        //this means that all elements in array are negative. Here the max_sum can be made equal to the largest number in the array, or simply 0, as the need might be.  
      
     } 
 
    //At this point maximum_sum holds the value of sum and begin_index and end_index would hold the indices. 
     * 
     * int localsum = 0;
int globalsum = 0;
for (i = 0; i < n; ++i)
{
localsum +=a[i];

if (localsum > global)
globalsum = localsum;
else if (localsum <0)
localsum = 0;
}
     * 
		 * 
		 * 
		 * 
		 * 
		 * 
		 * */
	}

	public static void findBitsOnInAnInt(int num)
	{
		int count = 0;
		for (int i = 0; i < 31; i++)
		{
			if ((num & (1 << i)) != 0)
			{
				count++;
				System.out.print("1 ");
			} else
			{
				System.out.print("0 ");
			}
		}
		System.out.println("# of Bits Flagged: " + count);
	}

	public static void findFlaggedBitsSparse(int num)
	{
		int count = 0;
		while (num != 0)
		{
			num &= (num - 1);
			count++;
		}
		System.out.println("# of Bits Flagged: " + count);
	}
	
	public static void findFlaggedBitsDense(int num)
	{
		int count = 0;
		while (num != 0)
		{
			if ((num & 1) == 1)
			{
				count++;
			}
			num >>= 1;
		}
		System.out.println("# of Bits Flagged: " + count);
	}
}
